package tree;

import java.util.Stack;

/**
 * @Author wangtengyu
 * @Create 2018-09-13-15:31 //打印二叉树中和为输入的值的路径 跟节点到达叶节点
 *
 * 画出一个完成的查找过程所包含的操作 是否叶节点，路径 让问题清晰
 */
public class printSumRoute {

  public void printSumRoute(IntTreeNode root, int expectSum) {
    if (root == null) {
      return;
    }

    //定义数字
    int currentSum = 0;
    Stack<Integer> RouteStack = new Stack<>();
    printSumRoute(root, expectSum, currentSum, RouteStack);
  }

  private void printSumRoute(IntTreeNode root, int expectSum, int currentSum,
      Stack<Integer> RouteStack) {

    currentSum += root.getValue();
    RouteStack.add(root.getValue());

    //判断是否叶子节点
    boolean isLeaf = root.getLeft() == null && root.getRight() == null;

    //是叶子节点 是不是叶子节点的先后判断没关系
    if (currentSum == expectSum && isLeaf) {
      for (int path : RouteStack) {
        System.out.print(path + " ");
      }
      System.out.println();
    }

    //不是叶子节点
    if (!isLeaf) {
      if (root.getLeft() != null) {
        printSumRoute(root.getLeft(), expectSum, currentSum, RouteStack);
      }

      if (root.getRight() != null) {
        printSumRoute(root.getRight(), expectSum, currentSum, RouteStack);
      }
    }

    //注意 是叶子节点，无论相等不相等，都要返回上一层，返回上一层路径就减1，值也相应的减少
    //只不过是叶子节点，值相等的时候打印
    currentSum -= root.getValue();
    RouteStack.pop();


  }


  public static void main(String[] args) {
    IntTreeNode root = new IntTreeNode(10);
    root.setLeft(new IntTreeNode(5));
    root.getLeft().setLeft(new IntTreeNode(4));
    root.getLeft().setRight(new IntTreeNode(7));
    root.setRight(new IntTreeNode(12));

    printSumRoute printSumRoute = new printSumRoute();
    printSumRoute.printSumRoute(root, 22);
  }
}
